package datastructure.array;

import java.util.ArrayList;
import java.util.List;

/**
 * Intersect two sorted arrays
 *
 * @author Lei Zhang
 */
public class IntersectArrays {

  public static List<Integer> intersectTwoSortedArrays(int[] a1, int[] a2) {
    if (a1 == null || a2 == null) {
      throw new IllegalArgumentException("null");
    }

    List<Integer> retList = new ArrayList<Integer>();
    int i = 0;
    int j = 0;
    while (i < a1.length && j < a2.length) {
      if (a1[i] == a2[j]) {
        retList.add(a1[i]);
        i++;
        j++;
      } else if (a1[i] < a2[j]) {
        i++;
      } else {
        j++;
      }

    }

    return retList;
  }

  public static void main(String args[]) {

    int[] anArray1 = {
      2,
      5,
      7,
      8,
      10,
      16,
      17,};

    int[] anArray2 = {
      3,
      5,
      7,
      9,
      10,
      16,
      19,};


    System.out.println(IntersectArrays.intersectTwoSortedArrays(anArray1,
        anArray2));

  }
}
